package org.example.myleet.p872;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Assert.isTrue(solution.leafSimilar(parse(new Integer[]{3,5,1,6,2,9,8,null,null,7,4}), parse(new Integer[]{3,5,1,6,7,4,2,null,null,null,null,null,null,9,8})));
        Assert.isTrue(solution.leafSimilar(parse(new Integer[]{1}), parse(new Integer[]{1})));
        Assert.isTrue(!solution.leafSimilar(parse(new Integer[]{1}), parse(new Integer[]{2})));
        Assert.isTrue(solution.leafSimilar(parse(new Integer[]{1,2}), parse(new Integer[]{2,2})));
        Assert.isTrue(!solution.leafSimilar(parse(new Integer[]{1,2,3}), parse(new Integer[]{1,3,2})));
    }

    private static TreeNode parse(Integer[] input) {
        int idx = 0;
        TreeNode root = new TreeNode(input[idx++]);
        Queue<TreeNode> stack1 = new LinkedList<>();
        stack1.offer(root);
        Queue<TreeNode> stack2 = new LinkedList<>();
        while (idx < input.length) {
            while (!stack1.isEmpty()) {
                if (idx >= input.length) {
                    break;
                }
                TreeNode node = stack1.poll();
                if (input[idx] == null) {
                    node.left = null;
                } else {
                    node.left = new TreeNode(input[idx]);
                }
                ++idx;
                if (idx >= input.length) {
                    break;
                }
                if (input[idx] == null) {
                    node.right = null;
                } else {
                    node.right = new TreeNode(input[idx]);
                }
                ++idx;
                if (node.left != null) {
                    stack2.offer(node.left);
                }
                if (node.right != null) {
                    stack2.offer(node.right);
                }
            }
            Queue<TreeNode> t = stack1;
            stack1 = stack2;
            stack2 = t;
        }
        return root;
    }
}
